package datatypes.list;

import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

/**
 * This implementation of a doubly linked list is indexable.
 * @author nils
 *
 * @param <E>
 */
public class DoublyLinkedList<E extends Node<E>> implements List<E> {
	private int size = 0;
	E head = null;
	E tail = null;
	Object[] indexArray;
	boolean indicesUpToDate = false;
	
	public void updateIndices() {
		synchronized (this) {
			indexArray = new Object[this.size];
			Node<E> node = head;
			for (int i = 0; i < indexArray.length; i++) {
				indexArray[i] = node;
				node = node.getNext();
			}
			indicesUpToDate = true;
		}
	}

	@Override
	public boolean add(E element) {
		if (head == null) {
			head = element;
			tail = element;
		} else {
			element.setPrevious(tail);
			tail.setNext(element);
			tail = element;
		}
		size++;
		indicesUpToDate = false;
		return true;
	}
		
	public E headNode() {
		return head;
	}

	@Override
	public void add(int arg0, E arg1) {
		System.out.println("add(int, E) not supported.");
		throw new UnsupportedOperationException();
	}

	@Override
	public boolean addAll(Collection<? extends E> collection) {
		System.out.println("addAll(Collection<? extends E>) not supported.");
		throw new UnsupportedOperationException();
	}
	
	public boolean addAll(DoublyLinkedList<? extends E> toBeAdded) {
		if (toBeAdded.size == 0) {
			return true;
		}
		this.size += toBeAdded.size;
		this.tail.setNext(toBeAdded.head);
		toBeAdded.head.setPrevious(this.tail);
		this.tail = toBeAdded.tail;
		indicesUpToDate = false;
		return true;
	}

	@Override
	public boolean addAll(int arg0, Collection<? extends E> arg1) {
		System.out.println("addAll(int, Collection<? extends E>) not supported.");
		throw new UnsupportedOperationException();
//		return false;
	}

	@Override
	public void clear() {
		head = null;
		tail = null;
		size = 0;
		indicesUpToDate = false;
	}

	@Override
	public boolean contains(Object o) {
		System.out.println("contains(Object) not supported.");
		throw new UnsupportedOperationException();
	}

	@Override
	public boolean containsAll(Collection<?> objects) {
		System.out.println("containsAll(Collection<?>) not supported.");
		throw new UnsupportedOperationException();
	}

	/**
	 * returns the Element of the node at the specified index.
	 * This method returns in O(n) time if the indices are out of date, otherwise
	 * in O(1) time. Therefore it is a good strategy to group indexed access to
	 * the list inside code that does not mutate this list. E.g., if indexed access is within a
	 * loop and some elements have to be deleted from the list, it is typically much
	 * faster to collect the items to be removed and remove them from the list outside
	 * of the loop.
	 * WARNING: the indices do not necessarily reflect the
	 * order of this list!!!
	 */
	@SuppressWarnings("unchecked")
	@Override
	public E get(int index) {
		if ( ! indicesUpToDate) {
			updateIndices();
		}
		E element = (E)indexArray[index];
		return element;
	}

	@Override
	public int indexOf(Object o) {
		System.out.println("indexOf(Object) not supported.");
		throw new UnsupportedOperationException();
	}

	@Override
	public boolean isEmpty() {
		return size == 0;
	}

	@Override
	public Iterator<E> iterator() {
		DoublyLinkedListIterator<E> iterator = new DoublyLinkedListIterator<E>(head);
		return iterator;
	}

	@Override
	public int lastIndexOf(Object arg0) {
		System.out.println("lastIndexOf(Object) not supported.");
		throw new UnsupportedOperationException();
//		return 0;
	}

	@Override
	public ListIterator<E> listIterator() {
		System.out.println("listIterator() not supported.");
		throw new UnsupportedOperationException();
//		return null;
	}

	@Override
	public ListIterator<E> listIterator(int index) {
		System.out.println("listIterator(int) not supported.");
		throw new UnsupportedOperationException();
//		return null;
	}
	
	@Override
	public boolean remove(Object o) {
		System.out.println("remove(Object) not supported.");
		throw new UnsupportedOperationException();
	}
	
	public boolean remove(E node) {
		if (node == head) {
			head = head.getNext();
		}
		if (node == tail) {
			tail = tail.getPrevious();
		}
		node.remove();
		indicesUpToDate = false;
		size--;
		return true;
	}

	@Override
	public E remove(int index) {
		System.out.println("remove(Index) not supported.");
		throw new UnsupportedOperationException();
	}

	@Override
	public boolean removeAll(Collection<?> arg0) {
		System.out.println("removeAll(Collection<?>) not supported.");
		throw new UnsupportedOperationException();
//		return false;
	}

	@Override
	public boolean retainAll(Collection<?> arg0) {
		System.out.println("retainAll(Collection<?>) not supported.");
		throw new UnsupportedOperationException();
//		return false;
	}

	@Override
	public E set(int arg0, E arg1) {
		throw new UnsupportedOperationException();
//		return null;
	}

	@Override
	public int size() {
		return size;
	}

	@Override
	public List<E> subList(int arg0, int arg1) {
		throw new UnsupportedOperationException();
//		return null;
	}

	@Override
	public Object[] toArray() {
//		throw new UnsupportedOperationException();
		if ( ! indicesUpToDate) {
			updateIndices();
		}
		return indexArray;
	}

	@Override
	public <T> T[] toArray(T[] arg0) {
		throw new UnsupportedOperationException();
//		return nodes.toArray(arg0);
	}

}
